{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flip String to Monotone Increasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minFlipsMonoIncr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将字符串翻转到单调递增"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个二进制字符串，是以一些 <code>0</code>（可能没有 <code>0</code>）后面跟着一些 <code>1</code>（也可能没有 <code>1</code>）的形式组成的，那么该字符串是 <strong>单调递增 </strong>的。</p>\n",
    "\n",
    "<p>给你一个二进制字符串 <code>s</code>，你可以将任何 <code>0</code> 翻转为 <code>1</code> 或者将 <code>1</code> 翻转为 <code>0</code> 。</p>\n",
    "\n",
    "<p>返回使 <code>s</code> 单调递增的最小翻转次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"00110\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>翻转最后一位得到 00111.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"010110\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>翻转得到 011111，或者是 000111。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"00011000\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>翻转得到 00000000。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flip-string-to-monotone-increasing](https://leetcode.cn/problems/flip-string-to-monotone-increasing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flip-string-to-monotone-increasing](https://leetcode.cn/problems/flip-string-to-monotone-increasing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"00110\"', '\"010110\"', '\"00011000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt0 = s.count('0')#当前位置以及之后有几个0\n",
    "        cnt1 = 0#当前位置之前有几个1\n",
    "        res = n - cnt0#一开始默认全翻转为0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                cnt0 -= 1\n",
    "            elif c == '1':\n",
    "                res = min(res, cnt0 + cnt1)\n",
    "                cnt1 += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        s,t=0,1\n",
    "        for i in range(0,len(S)):\n",
    "            if S[i]=='1' :\n",
    "                s+=1\n",
    "            elif t>(2*s-i) :\n",
    "                t=2*s-i\n",
    "        return t+len(S)-s-1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import sys\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        C=Counter(S)\n",
    "        ones,zeros,res=0,0,sys.maxsize\n",
    "        res=min(res,C['0'])\n",
    "        for i in S:\n",
    "            if i=='1':\n",
    "                ones+=1\n",
    "            else:\n",
    "                zeros+=1\n",
    "            res=min(res,ones+C['0']-zeros)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(S)\n",
    "        cnt0 = S.count('0') # the number of zeros in the right\n",
    "        cnt1 = 0 # the number of ones in the left\n",
    "        res = length - cnt0\n",
    "        for i in range(length):\n",
    "            if S[i] == '0':\n",
    "                cnt0 -= 1\n",
    "            elif S[i] == '1':\n",
    "                res = min(res, cnt1 + cnt0)\n",
    "                cnt1 += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        output = 9999\n",
    "        prefix = [0 for i in range(len(S)+1)]\n",
    "        \n",
    "        for i in range(1, len(S)+1):\n",
    "            if S[i-1] == '1':\n",
    "                prefix[i] = prefix[i-1] + 1\n",
    "            else:\n",
    "                prefix[i] = prefix[i-1]\n",
    "                \n",
    "        for i in range(len(S)+1):\n",
    "            ans = (len(S) - i) - (prefix[len(S)] - prefix[i]) + prefix[i]\n",
    "            output = min(output, ans)\n",
    "        \n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "        if len(S) == 0:\n",
    "            return 0\n",
    "        count = []\n",
    "        indict = [1 if i=='1' else 0 for i in S]\n",
    "        count.append(len(S) - sum(indict))\n",
    "        for i in S:\n",
    "            if i == '0':\n",
    "                count.append(count[-1]-1)\n",
    "            else:\n",
    "                count.append(count[-1]+1)\n",
    "        # print(count)\n",
    "        return min(count)\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, string):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        zeros,ones=[],[]\n",
    "        # l,r \n",
    "        z,o=0,0\n",
    "        for i in string:\n",
    "            if i==\"1\":\n",
    "                z+=1\n",
    "            zeros.append(z)\n",
    "\n",
    "        for i in string[::-1]:\n",
    "            # print(\"-\"*10,o)\n",
    "            if i==\"0\":\n",
    "                o+=1\n",
    "            ones.insert(0,o)\n",
    "\n",
    "        # print(zeros,ones)\n",
    "        n=len(string)\n",
    "        mn=min(zeros[-1],ones[0])\n",
    "        for i in zip(zeros[:n-1],ones[1:]):\n",
    "            mn=min(mn,sum(i))\n",
    "        # print(mn)\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "        zero, one = 0, 0\n",
    "        for c in S:\n",
    "            if c == '1':\n",
    "                one, zero = min(zero, one), zero + 1\n",
    "            else:\n",
    "                one = min(zero + 1, one + 1)\n",
    "        return min(zero, one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "        N=len(S)\n",
    "        N_0=S.count(\"0\")  #total 0s\n",
    "        n_0=0 #current 0s\n",
    "        N_1=N-N_0\n",
    "        n_1=0\n",
    "        res=N_0\n",
    "\n",
    "        for i in range(len(S)):\n",
    "            if S[i]==\"0\":\n",
    "                n_0+=1\n",
    "            else:\n",
    "                n_1+=1\n",
    "            res=min(res,n_1+(N_0-n_0))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "\n",
    "        zero, one = 0, 0\n",
    "\n",
    "        for c in S:\n",
    "            if c == '1':\n",
    "                one = min(one, zero)\n",
    "                zero = zero + 1\n",
    "            else:\n",
    "                one = min(one + 1, zero + 1)\n",
    "\n",
    "        return min(one, zero)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "        r = S.count(\"0\")\n",
    "        t = r\n",
    "        for si in S:\n",
    "            if si == '1':\n",
    "                t += 1\n",
    "            else:\n",
    "                t -= 1\n",
    "            r = min(r, t)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "        L = len(S)\n",
    "        l, r = [0]*L, [0]*L\n",
    "        if S[0]==\"1\" : l[0]=1\n",
    "        if S[L-1]==\"0\": r[L-1]=1\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(1, L):\n",
    "            if S[i] == \"1\":\n",
    "                l[i] = l[i-1]+1\n",
    "            else: l[i] = l[i-1]\n",
    "        for i in range(L-2, -1,-1):\n",
    "            if S[i] == \"0\":\n",
    "                r[i] = r[i+1]+1\n",
    "            else: r[i] = r[i+1]\n",
    "        for i in range(L-1):\n",
    "            ans = min(l[i] + r[i+1], ans)\n",
    "        ans = min(l[L-1], ans)\n",
    "        ans = min(r[0], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, S: str) -> int:\n",
    "        P = [0]\n",
    "        for x in S: P.append(P[-1] + int(x))\n",
    "\n",
    "        return min(P[j] + len(S)-j-(P[-1]-P[j]) for j in range(len(P)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [0, 0] # 分别代表前面0和1出现的次数\n",
    "        for i in s:\n",
    "            if i == '1':\n",
    "                dp[1] += 1\n",
    "            else:\n",
    "                dp[0] = min(dp[0]+1,dp[1])\n",
    "        return min(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp0 = dp1 = 0\n",
    "        for c in s:\n",
    "            dp0New, dp1New = dp0, min(dp0, dp1)\n",
    "            if c == '1':\n",
    "                dp0New += 1\n",
    "            else:\n",
    "                dp1New += 1\n",
    "            dp0, dp1 = dp0New, dp1New\n",
    "        return min(dp0, dp1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        zeros = 0 if s[0]=='0' else 1\n",
    "        ans = 0\n",
    "        for i in range(1,n):\n",
    "            if s[i]=='0':\n",
    "                ans = min(ans+1,zeros)\n",
    "            zeros+=1 if s[i]=='1' else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        cnt = s.count('0')\n",
    "        res, tmp = cnt, cnt\n",
    "        for x in list(s):\n",
    "            if x == '1':\n",
    "                tmp += 1\n",
    "            else:\n",
    "                tmp -= 1\n",
    "            if tmp < res: \n",
    "                res = tmp\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        one_cnt = 0\n",
    "        ans = 0\n",
    "\n",
    "        for ch in s:\n",
    "            if ch == '1':\n",
    "                one_cnt += 1\n",
    "            elif ch == '0' and one_cnt >= 1:\n",
    "                one_cnt -= 1\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        ## dp0为以0为结尾的最小翻转次数\n",
    "        dp0 = 0 if s[0] == '0' else 1\n",
    "        ## dp1为以0为结尾的最小翻转次数\n",
    "        dp1 = 0 if s[0] == '1' else 0\n",
    "        for i in range(1, n):\n",
    "            v = s[i]\n",
    "            if v == '1':\n",
    "                ## 当前值为1的时候, 可以从dp0或者dp1递推过来\n",
    "                dp1 = min(dp0, dp1)\n",
    "                ## dp0需要翻转当前值,所以需要+1\n",
    "                dp0 = dp0 + 1\n",
    "            else:\n",
    "                ## 当前值=0, 所以dp1需要翻转当前值,然后从min(dp0, dp1)递推过来\n",
    "                dp1 = min(dp0, dp1) + 1\n",
    "        return min(dp0, dp1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        g=[0]*(n+10)\n",
    "        ng=0\n",
    "        ans=0\n",
    "        for x in s:\n",
    "            num=int(x)\n",
    "            cur=bisect_right(g,num,0,ng)\n",
    "            g[cur]=num\n",
    "            if cur==ng:\n",
    "                ng+=1\n",
    "        return n-ng\n",
    "\n",
    "        \n",
    "        \n",
    "        #宫水三叶思路\n",
    "        # #最长不下降子序列ans，n-ans\n",
    "        # n=len(s)\n",
    "        # #以i为结尾的最长递增子序列\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     if i<0:\n",
    "        #         return 0\n",
    "        #     ans=0\n",
    "        #     for j in range(i):\n",
    "        #         if ord(s[i])>=ord(s[j]):\n",
    "        #             ans=max(ans,dfs(j)+1)\n",
    "        #     return ans\n",
    "\n",
    "        # res=0\n",
    "        # for i in range(n):\n",
    "        #     res=max(dfs(i),res)\n",
    "        # return n-res-1\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        #自己的思路\n",
    "        #O(n)\n",
    "        #辅助数组g[i][1] 和 g[i][0] 记录包括当前数字的左1和右0的数目\n",
    "        #dp[i]表示以是以s[i]为分界线的最小反转次数\n",
    "        # n=len(s)\n",
    "        # g=[[0,0] for _ in range(n)]\n",
    "        # l=0\n",
    "        # r=n-1\n",
    "        # while l<n and r>=0:\n",
    "        #     x,y=s[l],s[r]\n",
    "        #     g[l][1]=(g[l-1][1] if l-1>=0 else 0)\n",
    "        #     g[r][0]=(g[r+1][0] if r+1<n else 0) \n",
    "        #     if x==\"1\":\n",
    "        #         g[l][1]+=1\n",
    "        #     if y==\"0\":\n",
    "        #         g[r][0]+=1         \n",
    "        #     l+=1\n",
    "        #     r-=1\n",
    "        # dp=[0]*n\n",
    "        # for i in range(n):\n",
    "\n",
    "        #     dp[i]=(g[i-1][1] if i-1>=0 else 0)+(g[i+1][0] if i+1<=n-1 else 0)\n",
    "        # return min(dp)\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[0]*2]*(n+1)\n",
    "        for i in range(n):\n",
    "            dp[i+1][1]=min(dp[i][0],dp[i][1])+(s[i]=='0')\n",
    "            dp[i+1][0]=dp[i][0]+(s[i]=='1')\n",
    "        return min(dp[n-1][0],dp[n-1][1])    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)+1\n",
    "        # def dfs(p,q):\n",
    "        #     if q==1:\n",
    "        #         ans=0\n",
    "        #         for i in range(p+1,n):\n",
    "        #             if s[i]=='0':\n",
    "        #                 ans+=1\n",
    "        #         return ans\n",
    "        #     else:\n",
    "        #         i=p+1\n",
    "        #         while i<n and s[i]=='0':\n",
    "        #             i+=1\n",
    "        #         if i==n:\n",
    "        #             return 0\n",
    "        #         return min(1+dfs(i,0),dfs(i,1))\n",
    "        s='0'+s\n",
    "        # return dfs(0,0)\n",
    "        dp=[[0,1]]+[[0,0]]*(n-1)\n",
    "        for i in range(1,n):\n",
    "            if s[i]=='0':\n",
    "                dp[i][1]=1+min(dp[i-1][0],dp[i-1][1])\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][1]=min(dp[i-1][0],dp[i-1][1])\n",
    "                dp[i][0]=1+dp[i-1][0]\n",
    "        return min(dp[n-1][0],dp[n-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefix(self, s):\n",
    "        zero = [0]\n",
    "        for char in s:\n",
    "            zero.append(zero[-1])\n",
    "            if char == '0':\n",
    "                zero[-1] += 1\n",
    "        return zero\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        zero = self.prefix(s)\n",
    "        res = len(s)\n",
    "        for i in range(len(s)):\n",
    "            temp = i - zero[i] + zero[-1] - zero[i]\n",
    "            res = min(temp, res)\n",
    "        res = min(res, len(s) - zero[-1])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n, cnts, cnt = len(s), [], 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '1': cnt += 1\n",
    "            cnts.append(cnt)\n",
    "        ans, cur = cnt, 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0': cur += 1\n",
    "            if i == 0: continue\n",
    "            tmp = cnts[i - 1] + cur\n",
    "            if ans == -1 or ans > tmp: ans = tmp\n",
    "        return min(ans, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)+1\n",
    "        # def dfs(p,q):\n",
    "        #     if q==1:\n",
    "        #         ans=0\n",
    "        #         for i in range(p+1,n):\n",
    "        #             if s[i]=='0':\n",
    "        #                 ans+=1\n",
    "        #         return ans\n",
    "        #     else:\n",
    "        #         i=p+1\n",
    "        #         while i<n and s[i]=='0':\n",
    "        #             i+=1\n",
    "        #         if i==n:\n",
    "        #             return 0\n",
    "        #         return min(1+dfs(i,0),dfs(i,1))\n",
    "        s='0'+s\n",
    "        # return dfs(0,0)\n",
    "        dp=[[0,1]]+[[0,0]]*(n-1)\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            if s[i]=='0':\n",
    "                print(i)\n",
    "                dp[i][1]=1+min(dp[i-1][0],dp[i-1][1])\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][1]=min(dp[i-1][0],dp[i-1][1])\n",
    "                dp[i][0]=1+dp[i-1][0]\n",
    "        return min(dp[n-1][0],dp[n-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        # 因为要把数字编程单调递增\n",
    "        # 所以遍历到0的时候，如果要保留0，则需要把前面的1全部变为0.\n",
    "        # 如果要翻转，那么翻转次数+=1\n",
    "        # 单调递增字串的前面的子串也是单调递增子串\n",
    "        # 动态规划：dp[i]表示i位及之前要变成单增数组的最小变化次数。\n",
    "        # 如果说遍历到s[i]=='1'，那么s[:i]一定是单调子串，dp[i] = dp[i-1]\n",
    "        # 如果s[i]=='0'，就会出现两种选择，第一种就是把它自己变成1，第二种就是把它之前的所有1变成0。\n",
    "        # 所以dp[i] = min(dp[i-1]+1, countone)\n",
    "        countone = 0\n",
    "        dp = [0]*len(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                if i>0: dp[i] = dp[i-1]\n",
    "                countone += 1\n",
    "            else:\n",
    "                if i==0: continue\n",
    "                dp[i] = min(dp[i-1]+1, countone)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        dp = [0]*n\n",
    "        cnt = 1 if s[0] == '1' else 0\n",
    "        for i in range(1,n):\n",
    "            if s[i] == '1':\n",
    "                dp[i] = dp[i-1]\n",
    "                cnt += 1\n",
    "            else:\n",
    "                dp[i] = min(cnt,dp[i-1]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def dfs(i, flag):\n",
    "            if i == n - 1:\n",
    "                return 0\n",
    "            ret = inf\n",
    "            for j in range(i+1, n):\n",
    "                if s[j] == '1':\n",
    "                    if ~flag:\n",
    "                        ret = min(dfs(j, flag) + 1, dfs(j, ~flag))\n",
    "                else:\n",
    "                    if flag:\n",
    "                        ret = dfs(j, flag) + 1\n",
    "            return ret\n",
    "        return dfs(-1, False)\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        tmp = [0] * (1 + n)\n",
    "        for i in range(1, n + 1):\n",
    "            tmp[i] += tmp[i-1] + (s[i-1] == '1')\n",
    "        ret = min(tmp[-1], n - tmp[-1])\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '1':\n",
    "                ret = min(ret, tmp[i] + n - i - 1 - tmp[-1] + tmp[i+1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = n\n",
    "        left_1_sum = [0 for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            left_1_sum[i] = left_1_sum[i - 1] + ord(s[i - 1]) - ord('0')\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            left_1_cnt = left_1_sum[i - 1]\n",
    "            right_0_cnt = (n - i) - (left_1_sum[n] - left_1_sum[i])  # 右边的数量 - 右边1的数量\n",
    "\n",
    "            # left_1_cnt + right_0_cnt，左边1翻转为0，右边0翻转为1的次数\n",
    "            ans = min(ans, left_1_cnt + right_0_cnt)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lastzero = [0] * n\n",
    "        lastone = [0] * n\n",
    "        if s[0] == '0':\n",
    "            lastone[0] = 1\n",
    "        else:\n",
    "            lastzero[0] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if s[i] == '1':\n",
    "                lastone[i] = min(lastzero[i-1], lastone[i-1])\n",
    "                lastzero[i] = lastzero[i-1]+1\n",
    "            else:\n",
    "                lastone[i] = lastone[i-1]+1\n",
    "                lastzero[i] = lastzero[i-1]\n",
    "        \n",
    "        # print(lastone, lastzero)\n",
    "        return min(lastone[-1], lastzero[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        flipCntOne = [0 for _ in range(len(s) + 1)]     # 表示到第 i 位为止要保持全 1, 需要翻转多少次\n",
    "        flipCntZero = [0 for _ in range(len(s) + 1)]    # xxx 全 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                flipCntOne[i+1] = flipCntOne[i] + 1\n",
    "                flipCntZero[i+1] = flipCntZero[i]\n",
    "            else:\n",
    "                flipCntOne[i+1] = flipCntOne[i]\n",
    "                flipCntZero[i+1] = flipCntZero[i] + 1\n",
    "        \n",
    "        # 分别检查最后一位变为 1 和变为 0 的情况下, 至少需要翻转多少次\n",
    "        # 注意, 如果最后一位要是 0, 那么前面必须全为 0\n",
    "        ans = len(s)\n",
    "        flipOneTotal = flipCntOne[-1]\n",
    "        for i in range(len(s)):\n",
    "            # flipCntOne[-1] - flipCntOne[i] 表示从第 i 位到最后一位保持 1 需要翻转多少次\n",
    "            # flipCntZero[i-1] 表示第 i 位以前保持 0 位需要翻转多少次\n",
    "            flipOneTotal = min(flipOneTotal, flipCntOne[-1] - flipCntOne[i+1] + flipCntZero[i])\n",
    "        return min(flipOneTotal, flipCntZero[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp0 = [0 for i in range(len(s) + 1)]\n",
    "        dp1 = [0 for i in range(len(s) + 1)]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp0[i] = dp0[i - 1]\n",
    "                dp1[i] = min(dp1[i - 1], dp0[i - 1]) + 1\n",
    "            else:\n",
    "                dp0[i] = dp0[i - 1] + 1\n",
    "                dp1[i] = min(dp1[i - 1], dp0[i - 1])\n",
    "        return min(dp1[-2], dp0[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        \n",
    "\n",
    "\n",
    "        # 结果字符串的前半部分是0， 后半部分是1\n",
    "        # dp0[i]表示第i个位置之后0的个数\n",
    "        # dp1[i]表示第i个位置之前1的个数\n",
    "        # 如果当前第i位为01之间的分界线，那么就是需要改变的个数就是dp0[i]+dp1[i]\n",
    "        l = len(s)\n",
    "        \n",
    "        def helper(s,ch):\n",
    "            dp_ch = [0]*len(s)\n",
    "            for i,c in enumerate(s):\n",
    "                if i==0:\n",
    "                    if c == ch:\n",
    "                        dp_ch[i] = 1\n",
    "                else:\n",
    "                    if c == ch:\n",
    "                        dp_ch[i] = dp_ch[i-1]+1\n",
    "                    else:\n",
    "                        dp_ch[i] = dp_ch[i-1]\n",
    "                # print(dp_ch, s, ch, c)\n",
    "            return dp_ch\n",
    "        \n",
    "        dp0 = helper(s[::-1], '0')\n",
    "        dp0 = dp0[::-1]\n",
    "        dp1 = helper(s, '1')\n",
    "        print(dp0, dp1)\n",
    "        ans = l\n",
    "        for i in range(l):\n",
    "            ans = min(dp0[i]+dp1[i]-1, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        if len(s) <= 1:\n",
    "            return 0\n",
    "        left_ones = [0 for _ in s] # 包含i,\n",
    "        right_zeros = [0 for _ in s] # 不包含i\n",
    "        one = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '1':\n",
    "                one += 1\n",
    "            left_ones[i] = one\n",
    "        \n",
    "        zero = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            right_zeros[i] = zero\n",
    "            if s[i] == '0':\n",
    "                zero += 1\n",
    "            \n",
    "        print(left_ones)\n",
    "        print(right_zeros)\n",
    "        rs = len(s)\n",
    "        for i in range(len(s)):\n",
    "            rs = min(rs, left_ones[i] + right_zeros[i])\n",
    "        return min(rs, zero, one)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "\n",
    "        s= list(int(x) for x in s)\n",
    "        ans=0\n",
    "\n",
    "        x0=[0]*len(s)\n",
    "        y1=[0]*len(s)\n",
    "\n",
    "        if s[0]==1:\n",
    "            x0[0]=1\n",
    "        else:\n",
    "            y1[0]=1\n",
    "        for j,v in enumerate(s[1:]):\n",
    "            i=1+j\n",
    "            if v==1:\n",
    "                x0[i]=x0[i-1]+1\n",
    "                y1[i]=min(x0[i-1],y1[i-1])\n",
    "            else:\n",
    "                x0[i]=x0[i-1]\n",
    "                y1[i]=min(x0[i-1],y1[i-1])+1      \n",
    "        # print(min(x0[-1],y1[-1])) \n",
    "        return min(x0[-1],y1[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        list1 = []\n",
    "        for i in range(len(s)):\n",
    "            if i == 0:\n",
    "                list1.append(int(s[i]))\n",
    "            else:\n",
    "                list1.append(list1[i-1]+int(s[i]))\n",
    "        # (len(s)-i) - (list1[-1]-list1[i]) + list[i]\n",
    "        list2 = [len(s)-i - list1[-1]+list1[i] + list1[i]-1 for i in range(len(list1))]\n",
    "        list2.append(len(s)-list1[-1])\n",
    "        list2.append(list1[-1])\n",
    "        return(min(list2))\n",
    "        # return list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l_ones, r_zeros = [0] * n, [0] * n\n",
    "        one = 0\n",
    "        for i in range(n):\n",
    "            l_ones[i] = one\n",
    "            one += s[i] == '1'\n",
    "        zero = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            zero += s[i] == '0'\n",
    "            r_zeros[i] = zero\n",
    "        return min(min(l_ones[i] + r_zeros[i] for i in range(n)), zero, one)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        ans = n\n",
    "        pre = [0] * (n + 1)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i, c in enumerate(s):\n",
    "            pre[i + 1] = pre[i] + (c == '1')\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf[i] = suf[i + 1] + (s[i] == '1')\n",
    "\n",
    "        def cal(s, i):\n",
    "            cnt_0, cnt_1 = n - i - (pre[n] - pre[i]), pre[n] - pre[i]\n",
    "            return n - i - max(cnt_0, cnt_1)\n",
    "        while i < n:\n",
    "            if s[i] == '1':\n",
    "                ans = min(ans, cal(s[i:], i) + pre[i])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        ln = len(s)\n",
    "        right_zero_count = [0]*(ln+1)\n",
    "        for i in range(ln-1,-1,-1):\n",
    "            if s[i] == '0':\n",
    "                right_zero_count[i] = right_zero_count[i+1]+1\n",
    "            else:\n",
    "                right_zero_count[i] = right_zero_count[i+1]\n",
    "        left_one_count = [0]*(ln+1)\n",
    "        for i in range(1,ln+1,1):\n",
    "            if s[i-1] == '1':\n",
    "                left_one_count[i] = left_one_count[i-1]+1\n",
    "            else:\n",
    "                left_one_count[i] = left_one_count[i-1]\n",
    "        res = [0]*(ln+1)\n",
    "        for i in range(ln+1):\n",
    "            res[i] = left_one_count[i]+right_zero_count[i]\n",
    "        # print(left_one_count)\n",
    "        # print(right_zero_count)\n",
    "        # print(res)\n",
    "        return min(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        prefix=[i for i in accumulate([int(x) for x in s],initial=0)]\n",
    "        nextfix=[i for i in accumulate([not int(x) for x in s[::-1]],initial=0)]\n",
    "        n=len(s)\n",
    "        pp=float(\"inf\")\n",
    "        for i in range(n+1):\n",
    "            if prefix[i]+nextfix[n-i]<pp:\n",
    "                pp=prefix[i]+nextfix[n-i]\n",
    "        return pp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    " \n",
    "        count_zeros=[0 for _ in range(n)]\n",
    "        for i in range(n-2,-1,-1):#该循环判断右边几个0，注意是倒序的\n",
    "            if s[i+1]=='0':\n",
    "                count_zeros[i]=count_zeros[i+1]+1\n",
    "            else:\n",
    "                count_zeros[i]=count_zeros[i+1]\n",
    "        count_ones=[0 for _ in range(n)]\n",
    "        for i in range(1,n):#该循环判断左边有几个1，正序\n",
    "            if s[i-1]=='1':\n",
    "                count_ones[i]=count_ones[i-1]+1\n",
    "            else:\n",
    "                count_ones[i]=count_ones[i-1]\n",
    "        ans=[0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ans[i]=count_ones[i]+count_zeros[i]\n",
    "\n",
    "        return min(ans)\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        l1 = list(itertools.accumulate(s, lambda x, c: x + (c == '1'), initial=0))\n",
    "        r0 = list(itertools.accumulate(s[::-1], lambda x, c: x + (c == '0'), initial=0))[::-1]\n",
    "        return min(l + r for l, r in zip(l1, r0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        ans = s.count('0')\n",
    "        l1 = [(0,ans)]\n",
    "        for c in s:\n",
    "            if(c == '0'):\n",
    "                l1.append((l1[-1][0], l1[-1][1] - 1))\n",
    "            elif(c == '1'):\n",
    "                l1.append((l1[-1][0] + 1, l1[-1][1]))\n",
    "        \n",
    "        for i in l1:\n",
    "            cur = i[0] + i[1]\n",
    "            if(ans > cur):\n",
    "                ans = cur\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0, 0] for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])+1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[1e9,1e9] for _ in range(n+1)]\n",
    "        dp[0] = [0,0]\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1]=='0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = 1 + min(dp[i-1])\n",
    "            else:\n",
    "                dp[i][1] = min(dp[i-1])\n",
    "                dp[i][0] = 1 + dp[i-1][0]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        s = (s + \"*\").strip(\"0\")[:-1]\n",
    "        s = (\"*\" + s).strip(\"1\")[1:]\n",
    "        if not s: return 0\n",
    "        \n",
    "        ## 1...0 \n",
    "        n = len(s)\n",
    "        dp = [[-1] * 2 for _ in range(n)]\n",
    "        dp[-1][0] = 0\n",
    "        dp[-1][1] = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if s[i] == \"1\":\n",
    "                dp[i][1] = dp[i+1][1]\n",
    "                dp[i][0] = dp[i+1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i+1][0]\n",
    "                dp[i][1] = dp[i+1][1] + 1\n",
    "\n",
    "        res = -1\n",
    "        for i in range(n+1):\n",
    "            if i == n:\n",
    "                tmp = dp[0][0]\n",
    "            else:\n",
    "                tmp = dp[i][1] + dp[0][0] - dp[i][0]\n",
    "            res = min(res,tmp) if res != -1 else tmp\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0, 0] for _ in s]\n",
    "        if s[0] == '0':\n",
    "            dp[0][1] = 1\n",
    "        else:\n",
    "            dp[0][0] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i] = [dp[i-1][0], min(dp[i-1])+1]\n",
    "            else:\n",
    "                dp[i] = [dp[i-1][0]+1, min(dp[i-1])]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0] * 2 for _ in range(len(s)+1)]\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for c in s:\n",
    "            i += 1\n",
    "            if c == '0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = dp[i-1][1] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = min(dp[i-1])\n",
    "        return min(dp[-1])\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        sLen = len(s)\n",
    "    \n",
    "        dp = [[0 for _ in range(2)] for _ in range(sLen)]\n",
    "        \n",
    "        if s[0] == '0':\n",
    "            dp[0][0] = 0\n",
    "            dp[0][1] = 1\n",
    "        else:\n",
    "            dp[0][1] = 0\n",
    "            dp[0][0] = 1\n",
    "        \n",
    "        for i in range(1, sLen):\n",
    "            if s[i] == '0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = min(dp[i-1][1], dp[i-1][0])\n",
    "\n",
    "        return min(dp[-1][0], dp[-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "\n",
    "        s = [eval(i) for i in s]\n",
    "        dp = [[0,0] for i in range(len(s))]\n",
    "        dp[0][0] = 0 if s[0]==0 else 1\n",
    "        dp[0][1] = 0 if s[0]==1 else 1\n",
    "        res = [min(dp[0][0],dp[0][1] )]\n",
    "\n",
    "        for i, v in enumerate(s):\n",
    "            if i==0:\n",
    "                continue\n",
    "            if v==0:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][0]+1, dp[i-1][1]+1)\n",
    "            elif v==1:\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "            res.append(min(dp[i][0], dp[i][1]))\n",
    "\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dq=[[0 for i in range(2)] for j in range(len(s)+1)]\n",
    "        l=len(s)\n",
    "        for i in range(1,l+1):\n",
    "            if s[i-1]=='0':\n",
    "                dq[i][0]=dq[i-1][0]\n",
    "                dq[i][1]=min(dq[i-1][0],dq[i-1][1])+1\n",
    "            else:\n",
    "                dq[i][1]=min(dq[i-1][1],dq[i-1][0])\n",
    "                dq[i][0]=dq[i-1][0]+1     \n",
    "        return min(dq[-1])       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0 for _ in range(2)] for _ in range(len(s))]\n",
    "        if s[0]=='0':\n",
    "            dp[0][1] = 1\n",
    "        else:\n",
    "            dp[0][0] = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]=='0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][1],dp[i-1][0])+1\n",
    "            elif s[i]=='1':\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1][1],dp[i-1][0])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        # dp[i][0] 将1 翻为0的最小次数\n",
    "        # dp[i][1] 将0 翻为1的最小次数\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[0][0] = 1 if s[0]==\"1\" else 0\n",
    "        dp[0][1] = 0 if s[0]==\"1\" else 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0] +int(s[i]==\"1\")\n",
    "            dp[i][1] =min(dp[i-1][1],dp[i-1][0])+ int(s[i]==\"0\")\n",
    "\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # dp = [[0, 0], [0, 0], [0, 0]......]一共length个\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "\n",
    "        #初始化\n",
    "        dp[0] = [0, 1] if s[0] == \"0\" else [1, 0]\n",
    "\n",
    "        # 中间值\n",
    "        for i, ch in enumerate(s[1:], 1):\n",
    "            if ch == \"0\":\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1]) + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = min(dp[i-1])\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[[0,0] for _ in range(len(s))]\n",
    "        dp[0][0]=(s[0]=='1')\n",
    "        dp[0][1]=(s[0]=='0')\n",
    "        for i in range(1,len(s)):\n",
    "            dp[i][0]=dp[i-1][0]+(s[i]=='1')\n",
    "            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+(s[i]=='0')\n",
    "        return min(dp[-1][0],dp[-1][1])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
